COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00008 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\parskip 6pt
\rm
\line{\sevenrm a07.tex[162,phy] \today\hfill}

\bigskip
\line{\bf The Logarithmic Inequality.\hfill}

\medskip
A useful convexity property is
$$\hbox{$\ln x≤x-1\,,$ with equality iff $x=1$,}$$
readily shown for $x>0$ by
$$\ln x=\int↓1↑x{1\over y}\,dy≤\int↓1↑xdy=x-1\,,$$
and for $x<0$ by
$$\ln(x)=-\int↓x↑1{1\over y}\,dy≤-\int↓x↑1\,dy=x-1\,.$$

We use it to prove inequalities incorporating logarithms, such as 
$$\sum↓{i=1}↑nx↓i\log x↓i≥\biggl(\sum x↓i\biggr)\log\left(\,{\sum↓{i=1}↑n}x↓i
\over n\,\right)\,.\eqno(\ast)$$
Here is a paradigmatic application. We prove that, if
$f(n)=1+{a\over n}f(a)+{{n-a}\over n}f(n-a)$ ($0<a<n$),
$f(a)≥\lg a$, $f(n-a)≥\lg (n-a)$, then
$f(n)≥\lg n$, with possible equality only when $a=n/2$. That is, we want to

Show $1+{a\over n}\lg a+{{n-a}\over n}\lg(n-a)≥\lg n$, with equality
only if $a=n/2$.

\smallskip\noindent
{\bf Step 1:} Put all terms on the downhill side of the equation:

Show $\lg n-1-{a\over n}\lg a-{{n-a}\over n}\lg (n-a)≤0$.

\smallskip\noindent
{\bf Step 2:} Convert all logs to natural logs:

Show $\ln n-\ln 2-{a\over n}\ln a-{{n-a}\over n}\ln (n-a)≤0$.

\smallskip\noindent
{\bf Step 3:} Make all coefficients non-negative:

Show $\ln n+\ln{1\over 2}+{a\over n}\ln{1\over a}+{{n-a}\over n}\ln{1\over{n-a}}
≤0$.

\smallskip\noindent
{\bf Step 4:} Combine terms so that all logs are zero in the cases where 
equality is obtained; in this case, where $a=n/2$:

Show ${a\over n}\left(\ln n+\ln{1\over 2}+\ln{1\over a}\right)+{{n-a}\over n}
\left(\ln n+\ln{1\over 2}+\ln{1\over{n-a}}\right)≤0$; that is,

Show ${a\over n}\ln{n\over{2a}}+{{n-a}\over n}\ln{n\over{2(n-a)}}≤ 0$.

\smallskip\noindent
{\bf Step 5:} Apply the logarithmic inequality to all logarithms.

${a\over n}\ln{n\over 2a}+{n-a\over n}\ln {n\over 2(n-a)}≤{a\over n}
\bigl({n\over 2a}-1\bigr)+{n-a\over n}\bigl({n\over 2(n-a)}-1\bigr)
={1\over 2}-{a\over n}+{1\over 2}-{n-a\over n}=0$.

\vfill\eject

%\bigskip
\noindent
{\bf Exercises:}

\smallskip
\disleft 38pt:(1):
Prove $(\ast)$.

\smallskip
\disleft 38pt:(2):
Prove if each $p↓{ij}>0$, $r↓i=\sum↓jp↓{ij}$, $s↓j=\sum↓ip↓{ij}$,
$t=\sum↓{ij}p↓{ij}$, then
$\sum↓{i,j}p↓{ij}\log p↓{ij}+t\log t≥\sum↓ir↓i\log r↓i+\sum↓js↓j\log s↓j$.

\smallskip
\disleft 38pt:(3):
Prove if $p$ and $q$ are complementary probabilities, then
$p\log p+2q\log q≥c$, where $c$ is the largest constant that works.

\smallskip
\disleft 38pt:(4):
Prove if $f(1)=0$, $f(n)=n+f(a↓n)+f(n-a↓n)$, then $f(n)≥n\lg n$.

\smallskip
\disleft 38pt:(5):
A binary tree has $n$ nodes. Find a prove a lower bound on
the sum of their distances from the root.

\vfill\eject

\noindent{\bf Solution.}

\disleft 38pt:(2):
Show $\sum r↓i\ln r↓i+\sum s↓j\ln s↓j-\sum p↓{ij}\ln p↓{ij}-t\ln t≤0$;

\disleft 38pt::
Show $\sum r↓i\ln r↓i+\sum s↓j\ln s↓j+\sum p↓{ij}\ln{1\over{p↓{ij}}}+t\ln{1\over t}
≤0$;

\disleft 38pt::
Show $\sum↓{ij}p↓{ij}\ln r↓i+\sum↓{ij}p↓{ij}\ln s↓j+\sum↓{ij}p↓{ij}\ln
{1\over{p↓{ij}}}+\sum↓{ij}p↓{ij}\ln{1\over t}≤0$;

\disleft 38pt::
 $\sum↓{ij}p↓{ij}\ln\left({{r↓is↓j}\over{t\,p↓{ij}}}\right)
≤\sum p↓{ij}\left({{r↓is↓j}\over{t\,p↓{ij}}}
-1\right)=\sum{{r↓is↓j}\over t}-\sum p↓{ij}={{t↑2}\over t}-t=0$.


\bigskip
\parindent0pt
\copyright 1986 Robert W. Floyd

First draft (not published)
January 30, 1986.
%revised: date;
%subsequently revised.

\bye